import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA
 * Description:
 * User: Administrator
 * Data: 2023 - 09 - 05
 * Time: 11:48
 */
//牛客 缺失的第一个正整数
public class Solution4 {
    //法一 我的方法
    public int minNumberDisappeared (int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] > 0) {
                map.put(nums[i], 1);
            }
        }
        int i = 1;
        for (; map.containsKey(i); i++) {

        }
        return i;
    }
    public int minNumberDisappeared1 (int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] > 0) {
                map.put(nums[i], 1);
            }
        }
        int i = 1;
        for (; map.containsKey(i); i++) {

        }
        return i;
    }




    //法二 官方推荐方法
    public int minNumberDisappeared2 (int[] nums) {
        int n = nums.length;
        HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>();
        //哈希表记录数组中出现的每个数字
        for(int i = 0; i < n; i++)
            mp.put(nums[i], 1);
        int res = 1;
        //从1开始找到哈希表中第一个没有出现的正整数
        while(mp.containsKey(res))
            res++;
        return res;
    }




    //法三 官方扩展方法 原地哈希
    public static int minNumberDisappeared3 (int[] nums) {//原地哈希，1~n中的数与0~1下标一一对应，将1~n里的各个数-1作为
        int n = nums.length;                              //数组的下标，将数组该下标下的元素乘-1使其变为负数。这样处理之后，
        //遍历数组                                         //如果某个数组下标下的元素为负数，则表示这个下标+1这个数在数组中
        for(int i = 0; i < n; i++)                       //是存在的
            //负数和零全部记为n+1
            if(nums[i] <= 0) {//可能出现绝对值>n的负数，也可能出现绝对值<=n的负数
                nums[i] = n + 1;
            }
        for(int i = 0; i < n; i++)//即负数和>n的数不要进入下面的if语句
            //对于1-n中的数字
            if(Math.abs(nums[i]) <= n) {//有可能nums[i]为>n的数但被修改为了绝对值>n的负数，绝对值>n的负数依然符合<=n的条件会造成错误，所以要加Math.abs(nums[i])
                nums[Math.abs(nums[i]) - 1] *= -1;//有可能nums[i]被修改为了负数，此时以负数-1为下标会导致数组越界，所以要加Math.abs(nums[i])
            }
        for(int i = 0; i < n; i++)
            //找到第一个元素不为负数的下标
            if(nums[i] > 0) {
                return i + 1;//当数组中出现负数和大于n的数，则缺失的第一个正整数一定是i+1；否则缺失的第一个正整数一定是n+1
            }
        return n + 1;
    }
    public static void main(String[] args) {
        int[] arr = new int[]{2,1,3,7,6,9,5,11};
        System.out.println(minNumberDisappeared3(arr));
    }
}
